# bubbleSort.py
import matplotlib.pyplot as plt
import matplotlib.animation as animation


# 执行冒泡排序，同时记录每一步的状态
def bubble_sort(arr):
    # 获取数组的长度
    n = len(arr)

    # 创建一个列表来保存数组在每一步的状态
    steps = []

    # 创建一个列表来保存每一步中的比较情况
    comparisons = []

    # 记录初始状态的数组
    steps.append(list(arr))  # 初始状态

    # 记录初始状态下没有进行比较
    comparisons.append((-1, -1))  # 初始状态没有比较

    # 开始进行冒泡排序
    for i in range(n):
        # 内层循环从头遍历到 n-i-1 位置，因为每一趟会把最大的数移到最后
        for j in range(0, n - i - 1):
            # 记录当前比较的两个元素的索引
            comparisons.append((j, j + 1))  # 记录比较的索引

            # 如果当前元素比下一个元素大，交换它们的位置
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # 记录交换后的数组状态
                steps.append(list(arr))  # 每次交换后记录状态
            else:
                # 如果没有交换，也记录当前的数组状态
                steps.append(list(arr))  # 即使没有交换也记录状态

    # 返回记录的所有数组状态和比较情况
    return steps, comparisons


def show_bubble_sort_animation():
    # 初始化数据
    n = 10  # 数组的长度
    array = [3, 6, 2, 8, 4, 1, 7, 5, 9, 0]  # 待排序的数组

    # 获取排序过程中的所有状态和比较情况
    steps, comparisons = bubble_sort(array)

    # 创建一个Matplotlib的图表和坐标轴
    fig, ax = plt.subplots()
    # 绘制柱状图，初始状态是数组的第一个状态
    bar_rects = ax.bar(range(len(array)), steps[0], align="edge")
    ax.set_xlim(0, n)  # 设置x轴的范围
    ax.set_ylim(0, int(max(array) * 1.1))  # 设置y轴的范围，比数组最大值稍大
    ax.set_title("Bubble Sort Visualization")  # 设置图表标题
    ax.set_xlabel("Index")  # 设置x轴标签
    ax.set_ylabel("Value")  # 设置y轴标签

    # 定义一个更新函数，用于更新动画中的每一帧
    def update_plot(step_index):
        step = steps[step_index]  # 当前步骤的数组状态
        comp = comparisons[step_index]  # 当前步骤的比较情况
        for rect, val in zip(bar_rects, step):
            rect.set_height(val)  # 更新柱子的高度
            rect.set_color('b')  # 将所有柱子颜色设置为蓝色
        if comp[0] != -1 and comp[1] != -1:
            bar_rects[comp[0]].set_color('r')  # 将比较的第一个柱子颜色设置为红色
            bar_rects[comp[1]].set_color('r')  # 将比较的第二个柱子颜色设置为红色
        return bar_rects

    # 创建动画
    anim = animation.FuncAnimation(
        fig, update_plot, frames=range(len(steps)), interval=1000, repeat=False
    )

    # 显示绘图
    # plt.show()


    return anim
